Search Results

Documents authored by Watanabe, Osamu

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.15
On Nonadaptive Security Reductions of Hitting Set Generators

Authors: Shuichi Hirahara and Osamu Watanabe

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
One of the central open questions in the theory of average-case complexity is to establish the equivalence between the worst-case and average-case complexity of the Polynomial-time Hierarchy (PH). One general approach is to show that there exists a PH-computable hitting set generator whose security is based on some NP-hard problem. We present the limits of such an approach, by showing that there exists no exponential-time-computable hitting set generator whose security can be proved by using a nonadaptive randomized polynomial-time reduction from any problem outside AM ∩ coAM, which significantly improves the previous upper bound BPP^NP of Gutfreund and Vadhan (RANDOM/APPROX 2008 [Gutfreund and Vadhan, 2008]). In particular, any security proof of a hitting set generator based on some NP-hard problem must use either an adaptive or non-black-box reduction (unless the polynomial-time hierarchy collapses). To the best of our knowledge, this is the first result that shows limits of black-box reductions from an NP-hard problem to some form of a distributional problem in DistPH. Based on our results, we argue that the recent worst-case to average-case reduction of Hirahara (FOCS 2018 [Hirahara, 2018]) is inherently non-black-box, without relying on any unproven assumptions. On the other hand, combining the non-black-box reduction with our simulation technique of black-box reductions, we exhibit the existence of a "non-black-box selector" for GapMCSP, i.e., an efficient algorithm that solves GapMCSP given as advice two circuits one of which is guaranteed to compute GapMCSP.
Cite as

Shuichi Hirahara and Osamu Watanabe. On Nonadaptive Security Reductions of Hitting Set Generators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.APPROX/RANDOM.2020.15,
  author =	{Hirahara, Shuichi and Watanabe, Osamu},
  title =	{{On Nonadaptive Security Reductions of Hitting Set Generators}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.15},
  URN =		{urn:nbn:de:0030-drops-126182},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.15},
  annote =	{Keywords: hitting set generator, black-box reduction, average-case complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.51
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction

Authors: Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We show that the counting class LWPP [S. Fenner et al., 1994] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques. The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., PP^{Legitimate Deck} = PP) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning, and Torán [J. Köbler et al., 1992] that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard. We additionally show on the one hand that our main LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection- and acceptance- gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the #P-based analog of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does.
Cite as

Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe. The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hemaspaandra_et_al:LIPIcs.MFCS.2018.51,
  author =	{Hemaspaandra, Edith and Hemaspaandra, Lane A. and Spakowski, Holger and Watanabe, Osamu},
  title =	{{The Robustness of LWPP and WPP, with an Application to Graph Reconstruction}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.51},
  URN =		{urn:nbn:de:0030-drops-96330},
  doi =		{10.4230/LIPIcs.MFCS.2018.51},
  annote =	{Keywords: structural complexity theory, robustness of counting classes, the legitimate deck problem, PP-lowness, the Reconstruction Conjecture}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.18
Limits of Minimum Circuit Size Problem as Oracle

Authors: Shuichi Hirahara and Osamu Watanabe

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
The Minimum Circuit Size Problem (MCSP) is known to be hard for statistical zero knowledge via a BPP-Turing reduction (Allender and Das, 2014), whereas establishing NP-hardness of MCSP via a polynomial-time many-one reduction is difficult (Murray and Williams, 2015) in the sense that it implies ZPP != EXP, which is a major open problem in computational complexity. In this paper, we provide strong evidence that current techniques cannot establish NP-hardness of MCSP, even under polynomial-time Turing reductions or randomized reductions: Specifically, we introduce the notion of oracle-independent reduction to MCSP, which captures all the currently known reductions. We say that a reduction to MCSP is oracle-independent if the reduction can be generalized to a reduction to MCSP^A for any oracle A, where MCSP^A denotes an oracle version of MCSP. We prove that no language outside P is reducible to MCSP via an oracle-independent polynomial-time Turing reduction. We also show that the class of languages reducible to MCSP via an oracle-independent randomized reduction that makes at most one query is contained in AM intersect coAM. Thus, NP-hardness of MCSP cannot be established via such oracle-independent reductions unless the polynomial hierarchy collapses. We also extend the previous results to the case of more general reductions: We prove that establishing NP-hardness of MCSP via a polynomial-time nonadaptive reduction implies ZPP != EXP, and that establishing NP-hardness of approximating circuit complexity via a polynomial-time Turing reduction also implies ZPP != EXP. Along the way, we prove that approximating Levin's Kolmogorov complexity is provably not EXP-hard under polynomial-time Turing reductions, which is of independent interest.
Cite as

Shuichi Hirahara and Osamu Watanabe. Limits of Minimum Circuit Size Problem as Oracle. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.CCC.2016.18,
  author =	{Hirahara, Shuichi and Watanabe, Osamu},
  title =	{{Limits of Minimum Circuit Size Problem as Oracle}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.18},
  URN =		{urn:nbn:de:0030-drops-58426},
  doi =		{10.4230/LIPIcs.CCC.2016.18},
  annote =	{Keywords: minimum circuit size problem, NP-completeness, randomized reductions, resource-bounded Kolmogorov complexity, Turing reductions}
}
Document
DOI: 10.4230/DagSemRep.374
The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141)

Authors: Andreas Goerdt, Pavel Pudlák, Uwe Schöning, and Osamu Watanabe

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Andreas Goerdt, Pavel Pudlák, Uwe Schöning, and Osamu Watanabe. The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141). Dagstuhl Seminar Report 374, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{goerdt_et_al:DagSemRep.374,
  author =	{Goerdt, Andreas and Pudl\'{a}k, Pavel and Sch\"{o}ning, Uwe and Watanabe, Osamu},
  title =	{{The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{374},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.374},
  URN =		{urn:nbn:de:0030-drops-152545},
  doi =		{10.4230/DagSemRep.374},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact